int Fibonacci_Search(int *a, int n, int key)
{
	int low, high, mid, i, k;
	low = 1;
	high = n;
	k = 0;
	while(n > F[k]-1)
		k++;
	for (i = 0; i < F[k]-1; ++i)
		a[i] = a[n];
	while(low <= high)
	{
		mid = low + F[k-1]-1;
		if (key < a[mid])
		{
			high = mid - 1;
			k = k - 1;
		}
		else if (key > a[mid])
		{
			low = mid + 1;
			k = k - 2;
		}
		else
		{
			if (mid <= n)
			{
				return mid;
			}
			else
				return n;
		}
	}
	return 0;
}
           //0 1 2 3 4 5 6 7  8  9  10
int F[11] = {0,1,1,2,3,5,8,13,21,34,55};